.data
_string:
	.asciiz "input:\n"
.text
.globl main
	j	main
queen:	
	addi	$sp,	$sp,	-20	#store a0-a3& ra
	sw	$ra,	12($sp)
	sw	$a2,	8($sp)
	sw	$a1,	4($sp)
	sw	$a0,	0($sp)
	#we need to store t0(i) in 16($sp)	
	addi 	$t0,	$zero,	1	#i=1
	bne	$a0,	$a1,	loop1	#if n==queen
	lw	$v0,	8($sp)		#v0=icount
	addi	$v0,	$v0,	1	#icount++
	lw	$ra,	12($sp)		#load ra
	addi 	$sp,	$sp,	20	#release stack
	jr	$ra
loop1:	lw	$a1,	4($sp)	
	slt	$t3,	$a1,	$t0	#if i>queen t3=1
	bnez	$t3	return		#if t3=1 return
	lw	$t1,	0($sp)		#t1=n
	sll	$t1,	$t1,	2	#t1=4*n
	add	$t1,	$t1,	$s0	#t1 is the address of site[n]
	sw	$t0,	0($t1)		#site[n]=i
	lw	$a0,	0($sp)		#a0=n
#	move	$a0	$a0		#valid(n)
	jal 	valid
	beqz	$v0,	eloop1		#if(valid
	lw	$a0,	0($sp)		#load a0
	addi	$a0,	$a0,	1	#n+1
	lw	$a1,	4($sp)		#load a2
	lw	$a2,	8($sp)		#load icount
	sw	$t0,	16($sp)		#save t0,because it will changed in next queen function
	jal	queen			#queen
	lw	$t0,	16($sp)
	sw	$v0,	8($sp)		#icount=v0
eloop1:	addi	$t0,	$t0,	1	#i++
	j	loop1	
return:	lw	$v0,	8($sp)
	lw	$ra,	12($sp)
	addi	$sp,	$sp,	20	#relese stack
	jr	$ra	
		
valid:	move	$t5,	$zero
	move	$v0,	$zero
loop2:	beq	$t5,	$a0,	return1	
	sub	$t8,	$a0,	$t5	#t8=a0-t5=n-i
	sll	$t6,	$t5,	2	#t6=4i
	sll	$t7,	$a0,	2	#t7=4n
	add	$t6,	$t6,	$s0	#t6 is address of site[i]
	add	$t7,	$t7,	$s0	#t7 is address of site[n]
	lw	$t6,	0($t6)		#t6=s[i]
	lw	$t7,	0($t7)		#t7=s[n]
	beq	$t6,	$t7,	return0
	sub	$t9,	$t6,	$t7	#t9=n-i
	beq	$t8,	$t9,	return0
	sub	$t9,	$t7,	$t6	#t9=i-n I use this way to obtain abs function
	beq	$t8,	$t9,	return0
	addi	$t5,	$t5,	1	#t5++
	j	loop2
return1:addi	$v0,	$zero,	1
	jr	$ra	
return0:jr	$ra
main:	
#print
	li	$v0,	4
	la	$a0,	_string
	syscall
#input
	li	$v0,	5
	syscall
	subi	$s0,	$gp,	0x8000	#site[n]
	move	$a0,	$zero		#queen(0,n,0)
	move	$a1,	$v0
	move	$a2,	$zero
	jal	queen
	move	$a0,	$v0
	addi	$v0,	$zero,	1	#print m
	syscall
